m,n=map(int,input().split())
lines=[]
vars={}

for i in range(0,m):
    line=input()
    lines.append(line)

for i in range(0,n):
    #此处不要使用split
    #因为value中可能含有空格
    line=input()
    start_index=line.find(" ")
    key,value=line[0:start_index],line[start_index+1:]
    key="{{ "+key+" }}"
    value=value[1:-1]
    vars[key]=value

result=[]

for i in range(0,m):
    line=lines[i]
    
    end_index=0
    start_index=0
    while True:
        start_index=line.find("{{",start_index)
        if start_index==-1:
            break
        end_index=line.find("}}",start_index+2)
        if end_index==-1:
            break

        s=line[start_index:end_index+2]
        r_k=""
        
        if vars.get(s) is not None:
            r_k=vars[s]

        line=line[0:start_index]+r_k+line[end_index+2:]
        
        start_index+=len(r_k)

    result.append(line)

for line in result:
    print(line)


